package com.algrithom.dp;

import java.util.Arrays;

public class Solution3 {
    
    private static final int[] prises = {1,5,8,9,10,17,17,20,24,30};
    
    public static void main(String[] args){
        System.out.println(maxPriceOne(4));
        System.out.println(maxPriceTwo(4,new int[4]));
        System.out.println(maxPriceThree(4));
    }
    
    private static int maxPriceOne(int n){
        int mp = -1;
        if (0 == n) {
            return 0;
        } else {
            for (int i = 1; i <= n; i++) {
                mp = Math.max(mp,prises[i - 1] + maxPriceOne(n - i));
            }
        }
        return mp;
    }
    
    private static int maxPriceTwo(int n,int[] bkp){
        int mp = -1;
        if (0 == n) {
            return 0;
        }
        if (bkp[n - 1] > 0) {
            return bkp[n - 1];
        }
        for (int i = 1; i <= n; i++) {
            mp = Math.max(mp,prises[i - 1] + maxPriceTwo(n - i,bkp));
        }
        bkp[n - 1] = mp;
        return mp;
    }
    
    private static int maxPriceThree(int n){
        int[] bkp = new int[n + 1];
        Arrays.fill(bkp,0);
        for (int i = 1; i <= n; i++) {
            int mp = -1;
            for (int j = 1; j <= i; j++) {
                mp = Math.max(mp,prises[j - 1] + bkp[i - j]);
            }
            bkp[i] = mp;
        }
        return bkp[n];
    }
}
